package NewCoder;

import java.util.ArrayList;
import java.util.Arrays;

public class BM56 {
    public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        ArrayList<Integer> res=new ArrayList<>();
        int n=num.length;
        Arrays.sort(num);
        boolean[] used=new boolean[n];
        dfs(list,res,n,num,used);
        return list;
    }
    private void dfs(ArrayList<ArrayList<Integer>> list,ArrayList<Integer> res,int len,int[] num,boolean[] used){
        if(res.size()==len){
            list.add(new ArrayList<>(res));
            return;
        }
        for(int i=0;i<len;i++){
            if(used[i]){
                continue;
            }
            if(i>0 && num[i]==num[i-1] && !used[i-1]){
                continue;
            }
            used[i]=true;
            res.add(num[i]);
            dfs(list,res,len,num,used);
            used[i]=false;
            res.remove(res.size()-1);

        }
    }
}
